#include <bits/stdc++.h>
using namespace std;
const int MaxN=51000, Mo=1e9+9, MM=255;
const int INF=1e8;

int N,M,D;
int a[MaxN],b[MaxN];
int f[MaxN][MM+7],g[MM+7];

inline int fix(int s){
    return (s+MM+1)&MM;
}

void dp(){
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    f[0][0]=1; g[0]=1;
    int pl=0, pr=0;
    for (int i=1; i<=N; i++){
        int l=lower_bound(b+1,b+M+1,a[i]-D+1)-b-1;
        int r=upper_bound(b+1,b+M+1,a[i]+D-1)-b-1;
        for (int j=l; j<=r; j++)
            f[i][fix(j)]=g[fix(min(j,pr))];
        memset(g,0,sizeof(g));
        for (int j=l; j<=r; j++) g[fix(j)]=(g[fix(j-1)]+f[i][fix(j)])%Mo;
        pl=l; pr=r;
    }
}

int main(){
    int t,cas=0;
    scanf("%d",&t);
    while (t--){
        scanf("%d%d%d",&N,&M,&D);
        int i,j,k;
        for (i=1; i<=N; i++) scanf("%d",a+i);
        for (i=1; i<=M; i++) scanf("%d",b+i);
        a[++N]=INF;
        dp();
        printf("Case #%d: %d\n",++cas,f[N][fix(M)]);
    }
    return 0;
}